package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 堆排序
 * 堆排序是指利用堆这种数据结构所涉及的一种排序算法。堆是一种近似完全二叉树的结构，并同时满足堆的性质：即子节点的值总是小于（或者大于）它的父节点
 * <p>
 * 算法步骤：
 * 1. 将初始待排序列(R1,R2,...,Rn)构建成大顶堆，此堆为初始的无序区；
 * 2. 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ……, Rn-1) 和新的有序区 (Rn), 且满足 R[1, 2, ……, n-1]<=R[n]；
 * 3. 由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2, ……, Rn-1) 调整为新堆，然后再次将 R [1] 与无序区最后一个元素交换，
 * 得到新的无序区 (R1, R2, ……, Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。
 * <p>
 * 算法分析
 * 稳定性 ：不稳定
 * 时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
 * 空间复杂度 ：O(1)
 *
 * @author Api
 * @date 2022/11/19 22:31
 */
public class HeapSort {

    static int heapLen;


    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void buildMaxHeap(int[] arr) {
        for (int i = (arr.length >> 1) - 1; i >= 0; i--) {
            heapify(arr, i);
        }
    }


    private static void heapify(int[] arr, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (right < heapLen && arr[right] > arr[largest]) {
            largest = right;
        }
        if (left < heapLen && arr[left] > arr[largest]) {
            largest = left;
        }

        if (largest != i) {
            swap(arr, largest, i);
            heapify(arr, largest);
        }
    }


    public static void heapSort(int[] arr) {
        heapLen = arr.length;
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapLen -= 1;
            heapify(arr, 0);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 14, 4, 5, 4, 7, 9, 54, 6, 12, 5};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
